package com.lsa.cormen.ch24.samples;

import java.io.IOException;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.lang.StringUtils;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.AdjGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class EdgeClassSample {
    
    private static int time = 0;
    
    public static void main(String[] args) throws IOException {
        AdjGraph<VData, EdgeClass> g = new AdjGraph<VData, EdgeClass>(true, 11, null, EdgeClass.UNKNOWN);
        
        for (int i = 0; i < g.nodeCount(); i++) {
            g.setNodeAttr(i, new VData(Color.WHITE));
        }
        
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(2, 5);
        g.addEdge(2, 9);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        g.addEdge(4, 2);
        
        g.addEdge(1, 6);
        g.addEdge(6, 7);
        g.addEdge(7, 5);
        g.addEdge(7, 9);
        g.addEdge(6, 8);
        g.addEdge(8, 9);
        g.addEdge(8, 10);
        
        LinkedList<String> events = new LinkedList<String>();
        dfs(g, 0, events);
        
        for (String e : events) {
            System.out.print(e);
        }
        System.out.println();
        
        TgfGraphFactory.saveGraphAsTgf(g, 
                new IConverter<VData,String>() {
                    @Override
                    public String convert(VData data) {
                        return "" + data.vertex + " d=" + data.d;
                    }
                }, 
                new IConverter<EdgeClass,String>() {
                    @Override
                    public String convert(EdgeClass data) {
                        return ""+data;
                    }
                }, "data/gen/small_tmp.tgf");
        
//        for (Integer u : topSorted) {
//            System.out.print(u + " ");
//        }
    }
    
    public static void dfs(AdjGraph<VData, EdgeClass> g, int u, LinkedList<String> events) {
        List<Integer> adj = g.adjacencyList(u);
        
        g.nodeAttr(u).vertex = u;
        g.nodeAttr(u).d = ++time;
        events.add(StringUtils.repeat(" ", g.nodeAttr(u).d-1) + "{"+u + " \n");
        g.nodeAttr(u).c = Color.GRAY;
        
        for (Integer v : adj) {
            if (Color.WHITE == g.nodeAttr(v).c) {
                g.setEdgeAttr(u, v, EdgeClass.TREE);
                dfs(g, v, events);
            }
            else if (Color.GRAY == g.nodeAttr(v).c) {
                g.setEdgeAttr(u, v, EdgeClass.BACK);
            }
            else if (Color.BLACK== g.nodeAttr(v).c) {
                if (g.nodeAttr(u).d < g.nodeAttr(v).d) {
                    g.setEdgeAttr(u, v, EdgeClass.FORWARD);
                }
                else {
                    g.setEdgeAttr(u, v, EdgeClass.CROSS);
                }
            }
        }
        g.nodeAttr(u).c = Color.BLACK;
        g.nodeAttr(u).f = ++time;
        events.add(StringUtils.repeat(" ", g.nodeAttr(u).d) + u + "}\n");
    }
    
    public static enum Color{
        WHITE,
        GRAY,
        BLACK
    }
    
    public static enum EdgeClass {
        UNKNOWN,
        TREE,
        BACK,
        FORWARD,
        CROSS
    }
    
    private static class VData {
        Color c;
        int vertex;
        
        int d; // discovery time
        int f; // finish time
        
        private VData(Color color) {
            this.c = color;
        }
    }
}
